import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class _23_合并k个有序链表 {


    @Test
    public void test(){
        List<String > list=new ArrayList<>();


    }

    /**
     * 暴力解法的思路：遍历链表数组，将所有的值放到一个数组中，然后将数组进行排序，然后在创建一个链表
     * 根据合并两个有序链表的方法，取出第一个链表，然后遍历链表数组，逐一去合并
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head=new ListNode(0);
        ListNode res=head;
        ListNode list1=lists[0];
        for (int i = 1; i < lists.length; i++) {
            while (list1!=null&&lists[i]!=null){
                if (list1.val<lists[i].val){
                    //将res指向list1
                    res.next=list1;
                    //res向前移动
                    res=res.next;
                    //list1的节点也向前移动
                    list1=list1.next;
                }else {
                    res.next=lists[i];
                    res=res.next;
                    lists[i]=lists[i].next;
                }
            }
            if (list1==null){
                res.next=lists[i];
            }else {
                res.next=list1;
            }
            list1=res;
        }
        return head.next;
    }

}
